package com.lw.leetcode.arr.b;

/**
 * Created with IntelliJ IDEA.
 * 2447. 最大公因数等于 K 的子数组数目
 *
 * @author liw
 * @version 1.0
 * @date 2022/10/24 10:29
 */
public class SubarrayGCD {

    public static void main(String[] args) {
        SubarrayGCD test = new SubarrayGCD();

        // 4
//        int[] arr = {9, 3, 1, 2, 6, 3};
//        int k = 3;

        // 7
        int[] arr = {320, 734, 2, 960};
        int k = 2;

        // 0
//        int[] arr = {4};
//        int k = 7;

        // 0
//        int[] arr = Utils.getArr(1000, 1, 1000000000);
//        int k = 2;
//        System.out.println(k);

        int i = test.subarrayGCD(arr, k);
        System.out.println(i);
    }

    public int subarrayGCD(int[] nums, int k) {
        int max = 0;
        int length = nums.length;
        int[][] arr = new int[length][length];
        for (int i = 0; i < length; i++) {
            int num = nums[i];
            if (num % k != 0) {
                arr[i][i] = -1;
                continue;
            }
            if (num == k) {
                max++;
            }
            arr[i][i] = num;
        }
        for (int i = length - 2; i >= 0; i--) {
            for (int j = i + 1; j < length; j++) {
                int t = arr[i][j - 1];
                if (arr[j][j] == -1 || t == -1) {
                    arr[i][j] = -1;
                    continue;
                }
                int v = find(nums[j], t);
                if (v == k) {
                    max++;
                }
                arr[i][j] = v;
            }
        }
        return max;
    }

    private int find(int a, int b) {
        if (b == 0) {
            return a;
        }
        return find(b, a % b);
    }

}
